﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._20
{
    public class Leetcode16
    {
        public void Test()
        {
            try
            {
                ThreeSumClosest(new int[] { 0, 2, 1, -3 }, 1);
                ThreeSumClosest(new int[] {1, 1, 1, 0 }, -100);
            }
            catch (Exception ex)
            { }
        }

        /*
         16. 3Sum Closest

            Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

             */
        public int ThreeSumClosest(int[] nums, int target)
        {
            Array.Sort(nums);

            int closestNum = int.MaxValue;
            int tempResult = 0;
            int tempClosest = 0;
            int iRet = 0;
            int tempA = 0, tempB = 0;
            for (int a = 0; a < nums.Length - 2; a++)
            {
                tempA = nums[a];
                tempResult = tempA;
                //因为排序后，如果第一个数已经离很远，那就不用再循环了
                if (target > 0)
                {
                    if (tempResult - target > closestNum)
                        break;
                }
                else if (tempResult > closestNum)
                    break;

                for (int b = a + 1; b < nums.Length - 1; b++)
                {
                    tempB = nums[b];
                    tempResult = tempA + tempB;
                    if (target > 0)
                    {
                        if (tempResult - target > closestNum)
                            break;
                    }
                    else if (tempResult > closestNum)
                        break;
                    for (int c = b + 1; c < nums.Length; c++)
                    {
                        tempResult = tempA + tempB + nums[c];
                        if (tempResult == target)
                        {
                            //等于target直接返回
                            return tempResult;
                        }
                        
                        tempClosest = GetDistance(target, tempResult);


                        if (tempClosest < closestNum)
                        {
                            iRet = tempResult;
                            closestNum = tempClosest;
                        }
                         
                    }                       
                }               

            }
            return iRet;
        }

        private int GetDistance(int target, int num)
        {
            if (target > num)
            {
                return target - num;
            }
            else if (target < num)
            {
                return num - target;
            }
            return 0;
        }
    }
}
